package graph;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Stack;

import tree.Node;
import tree.Tree;

/**
 * @uml.dependency   supplier="graph.Vertex"
 * @uml.dependency   supplier="tree.Tree"
 */
public class Graph {
	/**
	 * @uml.property  name="maxDegree"
	 */
	private int maxDegree;
	/**
	 * @uml.property  name="vertices"
	 * @uml.associationEnd  multiplicity="(0 -1)" elementType="graph.Vertex"
	 */
	private List<Vertex> vertices = new ArrayList<Vertex>();
	/**
	 * @uml.property  name="verticesPrime"
	 * @uml.associationEnd  multiplicity="(0 -1)" elementType="graph.Vertex"
	 */
	private List<Vertex> verticesPrime = new ArrayList<Vertex>();
	/**
	 * @uml.property  name="stack"
	 * @uml.associationEnd  multiplicity="(0 -1)" elementType="java.lang.String"
	 */
	private Stack<String> stack;
	/**
	 * @uml.property  name="tree"
	 * @uml.associationEnd  
	 */
	private Tree tree;
	public Graph() {
		this.maxDegree = 0;
	}

	public void addVertex(Vertex v) {
		if (!this.vertices.contains(v)){
			this.vertices.add(v);			
		}
	}

	/**
	 * @return
	 * @uml.property  name="maxDegree"
	 */
	public int getMaxDegree(){
		for (Vertex v : this.vertices) {
			if (v.getDegree() > this.maxDegree)
				this.maxDegree = v.getDegree();
		}
		return this.maxDegree;
	}
	
	public List<Vertex> getVertices() {
		return new ArrayList<Vertex>(vertices);
	}

	public Stack<String> getStack(){
		return this.stack;
	}
	
	/**
	 * @return
	 * @uml.property  name="tree"
	 */
	public Tree getTree(){
		return this.tree;
	}
	public void print() {
		for (Vertex v : this.vertices) {
			System.out.println(v.printNeighbours());
		}
	}

	public String toString() {
		return this.vertices.size() + " vertices : " + this.vertices.toString();
	}
	public String toStringSimple() {
		return this.vertices.toString();
	}
	public int toInt(){
		return Integer.valueOf(this.vertices.toString());
	}
	/**
	 * Generate a complete graph
	 * @param n
	 * @return
	 */
	public static Graph completeGraph(int n) {
		long start=System.currentTimeMillis();
		Graph g = new Graph();
		Vertex vertex;
		for (int i = 0; i < n; i++) {
			vertex=new Vertex();
			g.addVertex(vertex);
			vertex.addNeighbours(g.getVertices());
		}		
		long end=System.currentTimeMillis();		
		System.out.println("Time to generate a  complete graph ("+n+" vertices) : " + String.valueOf(end-start) + "ms");
		return g;
	}

	/**
	 * Generate a circle graph 
	 * @param n
	 * @return
	 */
	public static Graph circleGraph(int n){
		long start=System.currentTimeMillis();
		Graph g = new Graph();
		Vertex prev,curr,first;
		
		//initialize the first vertex of the circle
		first = new Vertex();
		g.addVertex(first);
		prev=first;
		for (int i = 0; i < n; i++) {
			curr=new Vertex();
			if(!(i<n))
				curr.addNeighbours(first);
			
			curr.addNeighbours(prev);
			prev=curr;
		}
		
		long end=System.currentTimeMillis();		
		System.out.println("Time to generate a circle graph ("+n+" vertices) : " + String.valueOf(end-start) + "ms");
		return g;
	}
	
	/**
	 * Generate a random graph 
	 * @param n
	 * @return
	 */
	public static Graph randomGraphSimple(int n) {
		long start=System.currentTimeMillis();

		Graph g = new Graph();
		for (int i = 0; i < n; i++) {
			g.addVertex(new Vertex());
		}

		Random r = new Random(System.currentTimeMillis());
		int proba = r.nextInt(n);
		for (Vertex v : g.getVertices()) {
			if (v.getDegree() > n)
				break;
			if (v.getDegree() < proba) {
				v.addNeighbours(g.getVertices().get(proba));
				proba = r.nextInt(n);
			}
		}
		long end=System.currentTimeMillis();
		System.out.println("Time to generate a simple graph ("+n+" vertices) : " + String.valueOf(end-start) + "ms");
		return g;
	}
	
	/**
	 * Generate a graph with no limit for the number of neighbors
	 * @param n
	 * @return
	 */
	public static Graph randomGraph(int n){
		return Graph.randomGraph(n, 0);
	}
	
	/**
	 * Generate a random graph, every vertex have a different number of neighbor, 
	 * in less case every vertex have no neighbors 
	 * @param n
	 * @param maxNeighbors
	 * @return
	 */
	public static Graph randomGraph(int n, int maxNeighbors) {
		long start=System.currentTimeMillis();

		Graph g = new Graph();
		for (int i = 0; i < n; i++) {
			g.addVertex(new Vertex());
		}
		
		Random r = new Random();
		maxNeighbors=(maxNeighbors==0)?g.getVertices().size()-1:maxNeighbors;
		int rMaxNeighbor, indexNeighbor;
		List<Vertex> neighbors;
		
		for (Vertex v : g.getVertices()) {
			if (v.getDegree() > n || v.getDegree()>maxNeighbors)
				break;
			
			neighbors=new ArrayList<Vertex>();
			rMaxNeighbor=r.nextInt(maxNeighbors);
			for (int i = 0; i < rMaxNeighbor; i++) {
				indexNeighbor=r.nextInt(g.getVertices().size()-1);
				if(!neighbors.contains(g.getVertices().get(indexNeighbor)))
					neighbors.add(g.getVertices().get(indexNeighbor));
				else
					i--;
			}
			v.addNeighbours(neighbors);
		}
		long end=System.currentTimeMillis();
		System.out.println("Time to generate a graph ("+n+" vertices) : " + String.valueOf(end-start) + "ms");
		return g;
	}
	
	/**
	 * Generate a graph, every vertex have the same number of neighbors
	 * @param n
	 * @param numberNeighbor
	 * @return
	 */
	public static Graph randomGraphStaticNumberNeighbor(int n, int numberNeighbor){
		long start=System.currentTimeMillis();
		
		Graph g = new Graph();
		for (int i = 0; i < n; i++) {
			g.addVertex(new Vertex());
		}
		
		Random r = new Random();
		numberNeighbor=(numberNeighbor==0)?g.getVertices().size()-1:numberNeighbor;
		int indexNeighbor;
		List<Vertex> neighbors;
		
		for (Vertex v : g.getVertices()) {
			if (v.getDegree() > n || v.getDegree()>numberNeighbor)
				break;
			
			neighbors=new ArrayList<Vertex>();
			
			for (int i = 0; i < numberNeighbor; i++) {
				indexNeighbor=r.nextInt(g.getVertices().size()-1);
				if(!neighbors.contains(g.getVertices().get(indexNeighbor))
						&& g.getVertices().get(indexNeighbor).numberNeighbour() <= numberNeighbor)
					neighbors.add(g.getVertices().get(indexNeighbor));
				else
					i--;
			}
			v.addNeighbours(neighbors);
		}

		long end=System.currentTimeMillis();
		System.out.println("Time to generate a graph with a static number of neighbor ("+n+" vertices, "+numberNeighbor+" neighbors) : " + String.valueOf(end-start) + "ms");
		return g;

	}
	
	/**
	 * Generate a graph in which every vertex are connected to a center vertex
	 * @param n
	 * @return
	 */
	public static Graph starGraph(int n){
		long start=System.currentTimeMillis();
		
		Graph g = new Graph();
		
		Vertex center = new Vertex();
		Vertex satellite;
		for (int i = 0; i < n; i++) {
			satellite=new Vertex();
			satellite.addNeighbours(center);
			g.addVertex(satellite);
		}
		
		long end=System.currentTimeMillis();
		System.out.println("Time to generate a star graph with a static number of neighbor ("+n+" vertices) : " + String.valueOf(end-start) + "ms");
		return g;

	}
	
	/**
	 * Generate a graph in which there is n group of 2 vertices connected to each, and every member of the group is connected to a center vertex
	 * @param n
	 * @return
	 */
	public static Graph friendlyGraph(int n){
		long start=System.currentTimeMillis();
		
		Graph g = new Graph();
		
		Vertex center = new Vertex();
		Vertex satellite1, satellite2;
		
		g.addVertex(center);
		for (int i = 0; i < n; i++) {
			satellite1=new Vertex();
			satellite2=new Vertex();
			satellite2.addNeighbours(center);
			satellite1.addNeighbours(satellite2);
			g.addVertex(satellite1);
			g.addVertex(satellite2);
		}
		
		long end=System.currentTimeMillis();
		System.out.println("Time to generate a star graph with a static number of neighbor ("+n+" vertices) : " + String.valueOf(end-start) + "ms");
		return g;

	}

	/**
	 * Generate a graph with inclusive square (start from v)
	 * @param n represent the number of square (square = v vertices)
	 * @param s represent size of square
	 * @return
	 */
	public static Graph inclusiveSquareGraph(int n, int s){
		long start=System.currentTimeMillis();
		
		Graph g = new Graph();
		
		List<Vertex> square, prev = null;
		
		for (int i = 0; i < n; i++) {
			square=new ArrayList<Vertex>();
			for (int j = 0; j < s; j++) {
				square.add(new Vertex());
			}
			if(prev!=null && prev.size()>0){
				for (int j = 0; j < s; j++) {
					square.get(j).addNeighbours(prev.get(j));
				}
			}
		prev=new ArrayList<Vertex>(square);
		for (Vertex vertex : square) {
			g.addVertex(vertex);
		}
		}
		
		
		long end=System.currentTimeMillis();
		System.out.println("Time to generate a inclusive square graph ("+n+" vertices) : " + String.valueOf(end-start) + "ms");
		return g;

	}
	
	/**
	 * Input is a directed graph or undirected graph
	 * Output tree decomposition of a graph
	 */
	public void treeDecomposition(){
		long start,end;
		
		//Transform the graph into a undirected graph if needed
		start=System.currentTimeMillis();
		transformToUndirectedGraph();
		end=System.currentTimeMillis();
		System.out.println("Time to transform to undirected graph : " + String.valueOf(end-start) + "ms");
		
		//grap reduction -> fill the stack
		start=System.currentTimeMillis();
		graphReduction(this.getMaxDegree()+2);
		end=System.currentTimeMillis();
		System.out.println("Graph reduction : " + String.valueOf(end-start) + "ms");
		
		//construct a tree from a stack
		start=System.currentTimeMillis();
		treeConstruction();
		end=System.currentTimeMillis();
		System.out.println("Time to construct the tree from the stack : " + String.valueOf(end-start) + "ms");
		
		//Test Reachability
		if(vertices.size()>1){
			Vertex u = vertices.get(0);
			Vertex v = vertices.get(vertices.size()-1);
			start=System.currentTimeMillis();
			boolean reach = tree.reachable(u, v);
			end=System.currentTimeMillis();
			System.out.println("Time to test Reachability ("+reach+") : "+ String.valueOf(end-start) + "ms");
		}
	}
	
	/**
	 * reduce the graph (decomposition)
	 * @param degre
	 * @return
	 */
	private void graphReduction(int degre){
		stack = new Stack<String>();
		verticesPrime=new ArrayList<Vertex>(vertices);
		for (int i = 0; i < degre; i++) {
			removeUpto(i);
		}
	}
	
	/**
	 * remove graph
	 * @param degre
	 * @return
	 */
	private void removeUpto(int degre){
		Vertex v;
		while(true){
			v=vertexDegreeLess(degre);
			if(v!=null){
				buildClique(v.getNeighbours());
				String label = new String(String.valueOf(v.getName()));
				for (int i = 0; i < v.getNeighbours().size(); i++) {
					label.concat(";");
					label.concat(String.valueOf(v.getNeighbours().get(i).getName()));
				}
				stack.add(label);
				
				for (Vertex neigh : v.getNeighbours()) {
					neigh.getNeighbours().remove(v);
				}
				this.verticesPrime.remove(v);
			}
			else
				break;
		}
	}
	
	/**
	 * check the whole list of vertex to check if one have a degree (number of neighbor) less than the parameter
	 * @param degre
	 * @return
	 */
	private Vertex vertexDegreeLess(int degre){
		for (Vertex v : this.verticesPrime) {
			if(v.numberNeighbour() <= degre)
				return v;
		}
		return null;
	}
	
	/**
	 * Build a clique from a list of vertex
	 * @param neighbour
	 */
	private void buildClique(List<Vertex> neighbour){
		for (Vertex v : neighbour) {
			for (Vertex n : neighbour) {
				v.addNeighbours(n);
			}
		}
	}
	
	/**
	 * Construct a tree from a stack
	 */
	private void treeConstruction(){
		System.out.println(stack.size());
		String[] root = new String[getVertices().size()];
		
		for (int i = 0; i < getVertices().size(); i++) {
			root[i]=getVertices().get(i).toString();
		}
		
		if(root.length==0)
			root=getStack().pop().split(";");
		
		tree = new Tree(new Node(root));
		String[] tmp;
		Tree target;
		while(!stack.empty()){
			tmp = stack.pop().split(";");
			target = tree.findBags(tmp);
			target.addChild(new Tree(target, new Node(tmp)));
		}
	}
	
	/**
	 * Transform a directed graph to an undirected
	 */
	private void transformToUndirectedGraph(){
	}
}
